#include <stdio.h>
#include <stdlib.h>

#define MAXLEN 25

typedef struct
{
    char ch[MAXLEN]; //默认第一个位置不存储元素
    int length;
} SString;

/*

KMP算法

朴素模式匹配的缺点：
当某些子串与模式串部分匹配时，
主串的扫描指针经常回溯，导致时间开销增加



*/

/*
next数组：当j=k且发现字符不匹配时，令j=next[k]
*/

int Index_KMP(SString S, SString T, int next[])
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j]; //模式串向后移动
        }
    }
    if (j > T.length)
    {
        return i - T.length; //匹配成功,返回T在模式串中的位置
    }
    else
        return 0;
}

void getNext(SString T, int *next)
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

void myGetNext(SString T, int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int MyKmp(SString S, SString T, int next[])
{
    int i = 1, j = 1;
    while (i < T.length && j < T.length)
    {
        if (S.ch[i] == S.ch[j] || j == 0)
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    return 0;
}

/*
如何求next数组
当第j个字符匹配失败时，由前1~j-1个字符组成的串记作S，则：
next[j]=S的最长相等前后缀长度+1
特别的：next[1]=0,next[2]=1

串的前缀：包含第一个字符，且不包含最后一个字符的子串
串的后缀：包含最后一个字符，且不包含第一个字符的子串


优化
求nextval数组
nextval[1]=next[1]=0
如果模式串第j个字符和第j-1个字符相等，那么将nextval[j-1]的值赋值给nextval[j],否则维持next[j]
*/

int main()
{
    printf("\n\n========================================================================我干\n\n");
    SString T;
    T.ch[1] = 'a';
    T.ch[2] = 'a';
    T.ch[3] = 'a';
    T.ch[4] = 'a';
    T.ch[5] = 'b';
    T.length = 5;
    int *next;
    getNext(T, next);
    for (int i = 1; i <= T.length; i++)
    {
        printf("%c\t", next[i]);
    }
    printf("\n\n========================================================================\n\n");
    return 0;
}